基于改进分支定价算法的器具取配送运输问题研究

doi:10.16097/j.cnki.1009-6744.2023.03.024 1

交通运输系统工程与信息 ›› 2023, Vol. 23 ›› Issue (3): 223-234.DOI: 10.16097/j.cnki.1009-6744.2023.03.024 1

基于改进分支定价算法的器具取配送运输问题研究

温斌宾¹，何世伟^*2，迟居尚²，金福才¹

1.中国铁道科学研究院集团有限公司，电子计算技术研究所，北京100081；2.北京交通大学，综合交通运输大数据应用技术交通运输行业重点实验室，北京100044

收稿日期:2023-02-14 修回日期:2023-03-19 接受日期:2023-03-28 出版日期:2023-06-25 发布日期:2023-06-23
作者简介:温斌宾(1998-)，男，山西太原人，研究实习员
基金资助:
国家自然科学基金(62076023); 中国国家铁路集团有限公司科技研究开发计划项目 (P2022X013)

Containers Allocation and Recycle Transportation Problem with an Improved Branch-and-price Algorithm

WEN Bin-bin¹, HE Shi-wei^*2, CHI Ju-shang², JIN Fu-cai¹

1. Institute of Computing Technology, China Academy of Railway Sciences Corporation Limited, Beijing 100081, China; 2. Key Laboratory of Transport Industry of Big Data Application Technologies for Comprehensive Transport, Beijing Jiaotong University, Beijing 100044, China

Received:2023-02-14 Revised:2023-03-19 Accepted:2023-03-28 Online:2023-06-25 Published:2023-06-23
Supported by:
National Natural Science Foundation of China(62076023); Science and Technology Research and Development Project of China National Railway Group (P2022X013)

摘要/Abstract

摘要： 为解决物流集装单元化背景下器具运输成本高且灵活性差问题，本文提出集装器具循环调拨与回收的运输方式，在此运输方式下的器具运输问题属于供需未匹配与需求可拆分的取送货车辆路径问题(USDSPDVRP)。为在准确描述问题的基础上使模型易于求解，提出两阶段建模思路，设计解决USDSPDVRP模型的改进分支定价算法，通过Dantzig-Wolfe分解将模型分解为选择运输方案使用数量的限制主问题与根据主问题结果生成新运输方案的子问题，并设计相适应的路径缩减策略改进算法，实现高效求解复杂子问题的目的。算例结果表明，提出的改进分支定价算法相比Gurobi求解器，求解时间平均减少了83.9%，求得的可行解与精确解目标值间隔平均为2.8%。并对比分析了循环运输与直达运输的运输效益指标，证明了循环调拨与回收的运输方式能够有效减少运输总费用和车辆使用数，提高车辆满载率。

关键词: 物流工程, 器具循环调拨与回收, 分支定价算法, 集装单元化, 同时取配送车辆路径

Abstract: Considering the drawback of high cost and poor flexibility of equipment transportation under containerization of logistics, a transportation mode of circular allocation and recovery of containers was proposed. In this transportation mode, the container transportation problem belongs to Unpaired Supply-Demand and Split Pickup and Delivery Vehicle Routing Problem (USDSPDVRP). With an accurate problem description, a two-stage model was proposed. And an improved branch pricing algorithm was designed to solve the USDSPDVRP model. The model is decomposed into a main problem of resolving the number of transport schemes used and a sub- problem model of generating new transport schemes based on the results of the main problem by Dantzig-Wolfe decomposition. To solve complex sub-problems efficiently, an appropriate path reduction strategy is designed. Results show that the proposed algorithm is effective. Compared with the result of the Gurobi solver, the average computational time is reduced by 83.9% , and the average gap between the feasible solution and the optimal solution is 2.8% . At the same time, a comparative analysis of cyclic dispatch transportation and direct transportation proves that the cyclic dispatch transportation can reduce the cost and the number of vehicles, and increase the load rating of vehicles.

Key words: logistics engineering, containers circulation allocation and recycle, branch-and-price algorithm, container unitized, pickup and delivery vehicle routing

中图分类号:

U116

温斌宾, 何世伟, 迟居尚, 金福才. 基于改进分支定价算法的器具取配送运输问题研究[J]. 交通运输系统工程与信息, 2023, 23(3): 223-234.

WEN Bin-bin, HE Shi-wei, CHI Ju-shang, JIN Fu-cai. Containers Allocation and Recycle Transportation Problem with an Improved Branch-and-price Algorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(3): 223-234.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/10.16097/j.cnki.1009-6744.2023.03.024 1

http://www.tseit.org.cn/CN/Y2023/V23/I3/223

参考文献

[1] Brindley C. Position is everything: rising transport costs make pallet logistics more critical for success[J]. Pallet Enterprise, 2011, 50(6): 24-28.

[2] Mak S L, Wong Y M, Ho K C, et al. Contemporary Green Solutions for the Logistics and Transportation Industry—With Case Illustration of a Leading Global 3PL Based in Hong Kong[J]. Sustainability, 2022, 14(14): 8777.

[3] Mock K W, Chin J F, Zarirah K W. Implementing Milkrun in Lean Production[J]. HBRP Publication, 2020, 3(1): 1-17.

[4] Wu D, Wu C. Research on the time-dependent split delivery green vehicle routing problem for fresh agricultural products with multiple time windows[J]. Agriculture, 2022, 12(6): 793.

[5] Chen Q, Li K, Liu Z. Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads[J]. Transportation Research Part E: Logistics and Transportation Review, 2014, 69(9):218-235.

[6] Xu D, Li K, Zou Xc. An unpaired pickup and delivery vehicle routing problem with multi-visit[J]. Transportation Research Part E: Logistics and Transportation Review, 2017, 103(7): 218-247.

[7] 徐东洋, 李昆鹏, 郑飘, 等. 多车场多车型多品类供需未匹配与可任意拆分取送货车辆路径问题优化[J]. 管理学报, 2020, 17(07): 1086-1095. [Xu D Y, Li K P, Zhen P, et al. The Optimization Research of Multi-Category Unpaired Supply-Demand and Arbitrary Split Pickup and Delivery Vehicle Routing Problem with Multi-Depot and Multi-Type Trucks[J]. Chinese Journal of Management, 2020, 17(07): 1086-1095.]

[8] 范厚明, 张轩, 任晓雪, 等. 多中心开放且需求可拆分的VRPSDP问题优化[J]. 系统工程理论与实践, 2021, 41(06): 1521-1534. [Fan H M, Zhang X, Ren X X, et al. Optimization of multi-depot open split delivery vehicle routing problem with simultaneous delivery and pick-up[J]. System Engineering—Theory & Practice, 2021, 41(06): 1521-1534.]

[9] Li Y. A Selective Many-to-Many Pickup and Delivery Problem With Handling Cost in the Omni-Channel Last-Mile Delivery[J]. IEEE Access, 2022, 10: 111284-111296.

[10] Ben T H, Absi N, Feillet D, et al. A branch‐and‐price algorithm for the vehicle routing problem with time windows on a road network[J]. Networks, 2018, 73(4):401-417.

[11] Yu Y, Wang S, Wang J, et al. A branch-and-price algorithm for the heterogeneous fleet green vehicle routing problem with time windows[J]. Transportation Research Part B Methodological, 2019, 122(4): 511-527.

[12] 聂庆慧, 龙秀江, 梁程, 等. 多约束条件下城市道路环卫车优化配置与路径规划[J]. 交通运输系统工程与信息, 2022, 22(05): 273-284. [Nie Q H, Long X J, Liang C, et al. Optimal Allocation and Routing of Sanitation Vehicles on Urban Roads Under Multiple Constraints[J] Journal of Transportation Systems Engineering and Information Technology, 2022, 22(05): 273-284.] [13] 季彬,周赛琦,张政.分支定价方法求解带二维装箱约束的车辆路径问题[J/OL].控制理论与应用:1-9[2023-02-10]. http://kns.cnki.net/kcms/detail/44.1240.TP.20211018.1101.004.html. [Ji B, Zhou S Q, Zhang Zh, Branch-and-price approach for solving the vehicle routing problem with two-dimensional loading constraints[J]. Control Theory & Applications, 1-9[2023-02-10]. http://kns.cnki.net/kcms/detail/44.1240.TP.20211018.1101.004.html.]

[14] 兰泽康, 何世伟, 黎浩东. 铁路网络列车运行调整的优化模型及其分支定价算法[J]. 交通运输系统工程与信息, 2018, 18(01): 179-185. [Lan Z K, He S W, Li H D, et al. Optimization Model and Branch-and-price Algorithm for Train Dispatching on a Railway Network[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(1):179-185.] [15] 迟居尚, 何世伟, 宋子龙, 等. 基于分支定价算法的双层轿运车运输问题[J]. 控制与决策, 2022, 37(01): 185-195. [Chi J S, He S W, Song Z L, et al. Research on the optimization of double stack car carriers transportation problem based on branch-and-price algorithm[J]. Control and Decision, 2022, 37(01): 185-195.]

基于改进分支定价算法的器具取配送运输问题研究

Containers Allocation and Recycle Transportation Problem with an Improved Branch-and-price Algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张锦, 朱红星, 申皓, 李国旗. 复杂环境下工程建设项目应急物流选址一路径问题研究[J]. 交通运输系统工程与信息, 2023, 23(3): 280-289.
[2]	郑琰, 贲宇姝, 王康得, 姜晓红. 物流企业的碳排放效率评价及驱动因素分析[J]. 交通运输系统工程与信息, 2023, 23(2): 11-21.
[3]	吴暖, 代焕杰, 李季涛, 蒋奇含. 考虑时间容忍度的冷链物流配送路径多目标优化[J]. 交通运输系统工程与信息, 2023, 23(2): 275-284.
[4]	石褚巍, 马昌喜, 麻存瑞. 基于两阶段鲁棒优化的可靠性物流网络设计[J]. 交通运输系统工程与信息, 2023, 23(2): 285-299.
[5]	闫芳, 邓德萍, 柴福良, 马艳芳. 考虑环境负效应的智能垃圾桶动态收运路径优化问题[J]. 交通运输系统工程与信息, 2023, 23(1): 265-274.
[6]	张英贵, 姚璎华, 高全, 雷定猷. 铁路集装箱混合货物平衡装载布局优化模型与算法[J]. 交通运输系统工程与信息, 2022, 22(2): 214-222.
[7]	姜晓红, 陈莎, 张毅. 物流企业碳排放总量与效率测算方法[J]. 交通运输系统工程与信息, 2022, 22(2): 313-321.
[8]	周小祥, 黄承锋. 农村物流末端共配联盟演化博弈及稳定性研究[J]. 交通运输系统工程与信息, 2022, 22(1): 265-272.
[9]	王清斌, 于江宁, 郑建风. 甩挂运输模式下新增运输任务的干扰管理模型[J]. 交通运输系统工程与信息, 2021, 21(6): 160-166.
[10]	柳伍生, 李旺, 周清, 迭纤. “无人机-车辆”配送路径优化模型与算法[J]. 交通运输系统工程与信息, 2021, 21(6): 176-186.
[11]	珠兰, 马潇, 刘卓凡. 时间依赖型绿色车辆路径问题研究[J]. 交通运输系统工程与信息, 2021, 21(6): 187-194.
[12]	奇格奇, 张子贤, 卫振林, 李宝文. 基于语义挖掘的快递运输货品风险评价研究[J]. 交通运输系统工程与信息, 2021, 21(4): 248-255.
[13]	杨森炎，宁连举，商攀. 基于时空状态网络的电动物流车辆路径优化方法[J]. 交通运输系统工程与信息, 2021, 21(2): 196-204.
[14]	杨华龙，辛禹辰，高浩然. 随机扰动项呈离散分布的库存路径和定价问题的模型与算法[J]. 交通运输系统工程与信息, 2021, 21(2): 211-216.
[15]	辛禹辰，施胜男，杨华龙. 基于订单拆分的线上到线下连锁门店配送优化模型[J]. 交通运输系统工程与信息, 2020, 20(5): 212-217.